For any finite colored graph we define the empirical neighborhood measure,which counts the number of vertices of a given color connected to a givennumber of vertices of each color, and the empirical pair measure, which countsthe number of edges connecting each pair of colors. For a class of models ofsparse colored random graphs, we prove large deviation principles for theseempirical measures in the weak topology. The rate functions governing our largedeviation principles can be expressed explicitly in terms of relativeentropies. We derive a large deviation principle for the degree distribution ofErd\H{o}s--R\'{e}nyi graphs near criticality.
展开▼
机译：对于任何有限的彩色图，我们定义了经验邻域测度，它计算与每种颜色的给定数目的顶点连接的给定颜色的顶点数，以及经验对测度，它计算连接每对颜色的边数。对于稀疏有色随机图的一类模型，我们证明了弱拓扑中这些经验测度的大偏差原理。可以用相对熵来明确表达控制我们的大偏差原理的速率函数。对于接近临界的Erd \ H {o} s--R \'{e} nyi图的次数分布，我们推导了一个大偏差原理。
展开▼
